//给你一个points 数组，表示 2D 平面上的一些点，其中 points[i] = [xi, yi] 。 
//
// 连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 ：|xi - xj| + |yi - yj| ，其中 |val| 表示 
//val 的绝对值。 
//
// 请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
//输出：20
//解释：
//
//我们可以按照上图所示连接所有点得到最小总费用，总费用为 20 。
//注意到任意两个点之间只有唯一一条路径互相到达。
// 
//
// 示例 2： 
//
// 
//输入：points = [[3,12],[-2,5],[-4,1]]
//输出：18
// 
//
// 示例 3： 
//
// 
//输入：points = [[0,0],[1,1],[1,0],[-1,1]]
//输出：4
// 
//
// 示例 4： 
//
// 
//输入：points = [[-1000000,-1000000],[1000000,1000000]]
//输出：4000000
// 
//
// 示例 5： 
//
// 
//输入：points = [[0,0]]
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 1 <= points.length <= 1000 
// -106 <= xi, yi <= 106 
// 所有点 (xi, yi) 两两不同。 
// 
// Related Topics 并查集 数组 最小生成树 
// 👍 160 👎 0

  
package com.zwy.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author zwy 
 */
public class MinCostToConnectAllPoints{
    public static void main(String[] args) {
        Solution solution = new MinCostToConnectAllPoints().new Solution();
        int[][] points= {{0,0},{2,2},{3,10},{5,2},{7,0}};
        solution.minCostConnectPoints(points);
      }
     
/**
 *时间复杂度为:
 * @author zwy 
 */ 
      //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
   private int res=Integer.MAX_VALUE;
    public int minCostConnectPoints(int[][] points) {
        LinkedList list=new LinkedList();
        int n=points.length;
        back(list,n,points);

        return res;
    }
    public void back(LinkedList<Integer>list,int n,int[][] points){
        int count=0;
        int lastX=0;
        int lastY=0;
        if(list.size()==n){
           count=0;
           lastX=points[list.get(0)][0];
           lastY=points[list.get(0)][1];
            for (int i = 1; i < list.size(); i++) {
                count+=Math.abs(points[list.get(i)][0]-lastX)+Math.abs(points[list.get(i)][1]-lastY);
                lastX=points[list.get(i)][0];
                lastY=points[list.get(i)][1];
            }
            res=Math.min(res,count);
        }

        for (int i = 0; i < n; i++) {
            if(list.contains(i)){
                continue;
            }
            list.add(i);
            back(list,n,points);
            list.removeLast();
        }
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}